//
//  146.LRU缓存机制.swift
//  Top600
//
//  Created by rjb on 2021/8/6.
//

import Foundation
// LRU的缓存机制。
// 最近最少使用
// 思路
// 1. 获取时遍历链表，并将其加入到链表头部 ，时间为o(n)，要想o(1)需用hash表（更快找到）
// 2. 设置时，如果未满，加入头部，如果已经满，移除尾部，并加入头部 时间为o(n),要想on(1) 必须用双向链表(更快移动到前面，不用寻找上一个节点)

public class LRUListNode {
    public var val: Int = -1
    public var key: Int = -1
    public var prev: LRUListNode?
    public var next: LRUListNode?
    public init(key: Int, val: Int) {
        self.key = key
        self.val = val
        self.next = nil
        self.prev = nil
    }
}

class LRUCache {
    var capacity: Int
    // 记录住头部，尾部能很大的提高处理方便
    var head: LRUListNode = LRUListNode(key: -1, val: -1)
    var tail: LRUListNode = LRUListNode(key: -1, val: -1)
    
    var map: [Int: LRUListNode] = [:]
    init(_ capacity: Int) {
        self.capacity = capacity
        head.next = tail
        tail.prev = head
    }
    func get(_ key: Int) -> Int {
        guard let node = map[key] else {
            return -1
        }
        moveToHead(node)
        return node.val
    }
    func put(_ key: Int, _ value: Int) {
        if let node = map[key] {
            node.val = value
            moveToHead(node)
        } else {
            // 容量不可以
            if map.keys.count >= capacity {
                if let node = deleteLast() {
                    map.removeValue(forKey: node.key)
                }
            }
            let node = LRUListNode(key: key, val: value)
            addToHead(node)
            map[node.key] = node
        }
    }
    // 移除变加入到头部
    func moveToHead(_ node: LRUListNode) {
        deleteNode(node)
        addToHead(node)
    }
    // 删除最后一个节点
    func deleteLast() -> LRUListNode? {
        guard let pre = tail.prev else {
            return nil
        }
        return deleteNode(pre)
    }
    // 删除指定节点
    @discardableResult
    func deleteNode(_ node: LRUListNode) -> LRUListNode? {
        node.prev?.next = node.next
        node.next?.prev = node.prev
        return node
    }
    // 添加节点到头部
    func addToHead(_ node: LRUListNode) {
        node.prev = head
        node.next = head.next
        head.next?.prev = node
        head.next = node
    }
}

class Solution146 {
    static func test() {
        let lruCache = LRUCache(1)
        lruCache.put(2, 1)
        print(lruCache.get(2))
//        lruCache.put(1, 1)
//        lruCache.put(2, 2)
//
//        print(lruCache.get(1))
//
//        lruCache.put(3, 3)
//
//        print(lruCache.get(2))
//        lruCache.put(4, 4)
//
//        print(lruCache.get(1))
//        print(lruCache.get(3))
//        print( lruCache.get(4))
    }
}
